/**
 * 
 */
package problem;


import com.sun.org.apache.bcel.internal.generic.DDIV;

/**
 * PD: 
 * 如果有一个等差数组,然后对这个数组里面的每个元素做如下操作 
	1. 如果这个元素是偶数,除以2, 然后得到的数字再分析是否是偶数,如果还是,继续除2,一直除到是奇数, 
	2. 如果这个元素是奇数,那么就保持原样 
	这样就得到了另外一个数组, 现在要求根据这个变换后的数组,能否得到变换前的数组,请描述下思路. 
	比如现在有个数组{1,2,3,4},变换后是{1,1,3,1},那么需要根据{1,1,3,1},得到1,2,3,4. 
 * @author Jun
 *
 */
public class ArithArray {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		ArithArray solution = new ArithArray();
		int[] transArr = {1,1,3,1};
		for(int i : transArr)
			System.out.printf("%d ", i);
		System.out.println();
		transArr = solution.Solve(transArr);
		System.out.println("After recover to the array");
		for(int i : transArr)
			System.out.printf("%d ", i);
		System.out.println();
		
	}
	
	/**
	 * 输入转化后的数组，返回原始数组
	 * @param transArr
	 * @return
	 */
	
	/***解法：分情况讨论，设原始等差数组首项a, 差值d
	 * 	1. a, d为偶数，
	 *  2. a，偶数；d，奇数；则原始数组偶数项都为奇数。
	 *  3. a奇，d偶；原始数组全为奇数。
	 *  4. a奇，d奇；原始数组奇数项为奇数。
	 *  考虑上述三种情况，计算d，最后得到ai.
	 */	
	public int[] Solve(int[] transArr){
		
		//[起始下标，间隔]，3个数组分别表示上述三种情况
		int[][] arr = {{1,2},{0,1},{0,2}};
		int d = 0;
		boolean Match = false; 
		
		for(int i=0; i<arr.length; i++){
			
			int start = arr[i][0];
			int ds = arr[i][1];
			Match = ComputeArith(transArr,start, ds);
			if(Match){
				d = (transArr[start+ds]-transArr[start])/ds;
				//还原原始数组
				if(start==1) transArr[0] = transArr[start]-d;			
				for(int j = start+1; j<transArr.length;j++){
					transArr[j] = transArr[j-1]+d;					
				}				
				break;
			}			
		}
		return transArr;
	}

	
	/**
	 * 判断某数组是否是等差数列
	 * @param arr
	 * @return
	 */
	public boolean ComputeArith(int[] arr,int start,int ds){
		
		boolean isArithData = true;
		int d = 0;
		int tmp = 0;
		
		if(arr.length > (start+ ds))
			d = arr[start+ds] - arr[start];
		if(d==0)return false;
		
		tmp = arr[start+ds];
		for(int i= start+2*ds; i<arr.length -1; i+=ds){			
			
			if((tmp+d)!=arr[i]){
				isArithData = false;				
				break;
			}
			tmp = arr[i];
		}		
		return isArithData;
	}
}
